10118. Mad scientist

Farmer John arranged n of his cows, each of which belongs to one of two breeds: Holsteins or Guernseys. He recorded this arrangement as a string of  characters, each of which is either H or G, respectively. Unfortunately, when the cows arrived at the farm and John lined them up again, the resulting string turned out to be different from the original one.

Let us denote these two strings by a and b, where a is the original string that Farmer John wanted to see, and b is the string obtained after the cows arrived. Farmer John asked his cousin Ben for help.

After several months of work, Ben created an amazing machine called MCBF-3000, which can select any substring and replace all G characters in it with H, and all H characters with G. Now Farmer John wants to know the minimum number of applications of this machine required to transform string b into string a. Help Farmer John solve this problem.

Input. The first line contains an integer n (1 ≤ n ≤ 1000) – the number of cows. The following two lines contain the strings a and b. Each string consists only of the characters H and G.

Output. Print the minimum number of applications of the MCBF-3000 machine required to transform string b into string a.

Sample input	Sample output
7 GHHHGHH HHGGGHH	2

SOLUTION

greedy

Algorithm analysis

Scan the strings a and b from left to right. Consider the positions where the characters of the two strings differ. Let i be the index of the first such position, where a_i ≠ b_i. This means that the character in string b at position i must be inverted. At this moment, we fix the beginning of the interval on which the machine is applied.

Next, continue moving to the right as long as the characters of the two strings differ; that is, for all indices k in the interval i ≤ k ≤ j, the condition a_k ≠ b_k holds. As soon as we encounter a position j + 1 such that a_j+1 = b_j+1, the current interval [i; j] ends. This interval is maximal with respect to inclusion: it cannot be extended either to the left or to the right.

Each such interval corresponds to exactly one application of the MCBF-3000 machine, since the machine inverts all characters in the selected substring, thereby fixing all mismatches within the interval simultaneously. Therefore, the answer to the problem is the number of such maximal intervals.

Example

For the given example, there are two non-overlapping intervals on which the MCBF-3000 machine must be applied.

Algorithm implementation

Read the input data.

cin >> n >> a >> b;

Store the length of the current mismatch interval in the variable cnt. In the variable res we accumulate the answer – the number of times the machine is applied.

res = cnt = 0;

Process the characters of the strings sequentially.

for (i = 0; i < n; i++)

If a_i ≠ b_i, increase cnt by one.

if (a[i] != b[i])

cnt++;

Otherwise (if a_i = b_i), the current mismatch interval ends: we reset cnt to zero and increment the interval counter res by one.

else

{

if (cnt > 0) res++;

cnt = 0;

}

If cnt > 0, this means that there is an unfinished mismatch interval at the end of the string, which also requires one application of the machine.

if (cnt > 0) res++;

Print the answer.

cout << res << endl;

Python implementation

Read the input data.

n = int(input())

a = input()

b = input()

Store the length of the current mismatch interval in the variable cnt. In the variable res we accumulate the answer – the number of times the machine is applied.

res = cnt = 0

Process the characters of the strings sequentially.

for i in range(n):

If a_i ≠ b_i, increase cnt by one.

if a[i] != b[i]: cnt += 1

Otherwise (if a_i = b_i), the current mismatch interval ends: we reset cnt to zero and increment the interval counter res by one.

else:

if cnt > 0: res += 1

cnt = 0

If cnt > 0, this means that there is an unfinished mismatch interval at the end of the string, which also requires one application of the machine.

if cnt > 0: res += 1

Print the answer.

print(res)